HDOJ 2544 【Dijkstra】最短路

【题目描述】

http://acm.hdu.edu.cn/showproblem.php?pid=2544

【思路】

啊就是最短路裸题…Dijkstra+heap

#include<cstdio>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;

const int Max=2100000;
typedef pair<int,int> Pair;
priority_queue<Pair,vector<Pair>,greater<Pair> > Q;

int n,tail,dis[200],head[200];

struct data
{
      int w,to,next;
}k,edge[21000];

void build(int u,int v,int x)
{
      edge[tail].w=x;
      edge[tail].to=v;
      edge[tail].next=head[u];
      head[u]=tail++;
}

void Dij()
{
      Pair s,u;
      int v,val;

      dis[1]=0;
      s.first=0;
      s.second=1;
      Q.push(s);

      while (!Q.empty())
      {
            u=Q.top();
            Q.pop();
            v=u.second;
            val=u.first;
            if (dis[v]<val) continue;

            for (int i=head[v];i!=-1;i=edge[i].next)
            {
                  k=edge[i];
                  if (dis[k.to]>dis[v]+k.w)
                  {
                        dis[k.to]=dis[v]+k.w;
                        Q.push(Pair(dis[k.to],k.to));
                  }
            }
      }
}

int main()
{
      int n,m,u,v,x;

      while (scanf("%d%d",&n,&m)!=EOF)
      {
            if (!n && !m) break;

            tail=0;
            for (int i=0;i<200;i++) head[i]=-1;
            for (int i=0;i<200;i++) dis[i]=Max;

            for (int i=1;i<=m;i++)
            {
                  scanf("%d%d%d",&u,&v,&x);
                  build(u,v,x);
                  build(v,u,x);
            }
            Dij();
            printf("%d\n",dis[n]);
      }

      return 0;
}